Backtracking

* * *

Back|tra|cking 〈[bæ̣ktrækıŋ] n.; - od. -s; unz.; EDVProgrammier- bzw. Suchstrategie, die von bestimmten Problempunkten ausgehend Lösungswege entwickelt, wobei der bis dahin aktuelle (Daten-)Bestand gesichert (u. gegebenenfalls rückverfolgt) wird, falls sich der Weg als eindeutig falsch erweist [engl., „Rückverfolgung“]

* * *

Backtracking
 
[dt. »Zurückverfolgung«] das, ein Problemlöseverfahren, bei dem versucht wird, Teillösungen eines Problems systematisch zu einer Gesamtlösung auszubauen. Falls in einem gewissen Stadium ein weiterer Ausbau einer vorliegenden Teillösung nicht mehr möglich ist (Sackgasse), werden einer oder mehrere der letzten Teilschritte rückgängig gemacht. Die dann erhaltene reduzierte Teillösung versucht man auf einem anderen Weg wieder auszubauen. Das Zurücknehmen von Schritten und erneute Vorangehen wird so lange wiederholt, bis eine Lösung des Problems gefunden ist oder bis man erkennt, dass das Problem keine Lösung besitzt.
 
Ein Beispiel für das Backtracking ist die Suche in einem Labyrinth. Das Labyrinth kann als Baum dargestellt werden, bei dem der Ausgangspunkt die Wurzel und jede Verzweigungsmöglichkeit einen Knoten darstellt. Kein, ein oder mehrere Wege im Baum führen dann zum Zielpunkt. Die Suche mit Backtracking beginnt, indem von der Wurzel aus von Knoten zu Knoten ein Weg eingeschlagen wird (z.B. »immer links abzweigen«). Gelangt man in eine Sackgasse, geht man einen Knoten zurück und probiert die nächste Verzweigungsmöglichkeit aus (z. B. »an dieser Stelle rechts abzweigen«), bis diese zum Ziel oder wieder in eine Sackgasse führt. In letzterem Fall geht man wieder einen Schritt zurück und geht die nächstmögliche Verzweigung an. Erst wenn alle Verzweigungen an einem Knoten in Sackgassen führen, springt man einen weiteren Knoten zurück. Auf diese Art und Weise wird der ganze Baum durchfahren, und falls es einen Zielpunkt, eine Lösung gibt, wird diese auch gefunden.
 
Das Backtracking ist ein sehr einfaches Verfahren, das nach der Methode Versuch und Irrtum (Trial and Error) arbeitet. Es wird eingesetzt, wenn die Teillösungen keinen Aufschluss über die Gesamtlösung liefern. Backtracking kommt z. B. bei der Problemlösung mithilfe künstlicher Intelligenz (KI) zum Einsatz. Auch die Lösungssuche bei Prolog verwendet Backtracking. Ab einer bestimmten Zahl von Verzweigungsebenen wird das Verfahren impraktikabel, da die Rechenzeit exponenziell zur Ebenenzahl zunimmt.

Universal-Lexikon. 2012.

Synonyme:

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Backtracking — is a type of algorithm that is a refinement of brute force search. [cite web | url=http://www.cse.ohio state.edu/ gurari/course/cis680/cis680Ch19.html#QQ1 51 128 Backtracking algorithms | title=CIS 680: DATA STRUCTURES: Chapter 19: Backtracking… …   Wikipedia

  • Backtracking — Der Begriff Rücksetzverfahren oder englisch Backtracking (deut. Rückverfolgung) bezeichnet eine mathematische Problemlösungsmethode innerhalb der Algorithmik. Backtracking arbeitet nach dem Prinzip der Tiefensuche Inhaltsverzeichnis …   Deutsch Wikipedia

  • Backtracking — Retour sur trace Le retour sur trace, appelé aussi backtracking en anglais, consiste à revenir légèrement en arrière sur des décisions prises afin de sortir d un blocage. La méthode des essais et erreurs constitue un exemple simple de… …   Wikipédia en Français

  • backtracking — grįžimų metodas statusas T sritis informatika apibrėžtis Algoritmavimo metodas, kai sprendimas grindžiamas variantų tikrinimu ir, pasiekus aklavietę, grįžimu vienu žingsniu atgal. Grįžimų metodas labiausiai taikomas sprendžiant labirinto tipo… …   Enciklopedinis kompiuterijos žodynas

  • backtracking — The backwards movement of RNA polymerase along the DNA template to a state more stable than that encountered when some base pairs disrupt the attachment of the 3′ end from the active transcription site …   Medical dictionary

  • Backtracking — Back|tra|cking 〈[bæ̣ktrækıŋ] n.; Gen.: od. s; Pl.: unz.; EDV〉 Programmier bzw. Suchstrategie, die von bestimmten Problempunkten ausgehend Lösungswege entwickelt, wobei der bis dahin aktuelle (Daten )Bestand gesichert (u. gegebenenfalls… …   Lexikalische Deutsches Wörterbuch

  • Backtracking — Suchmethode. 1. Prinzip: An denjenigen Punkten des Suchvorgangs, an denen zur Fortsetzung der Suche eine Auswahlentscheidung zwischen mehreren Möglichkeiten getroffen werden muss, wird zunächst der aktuelle Zustand festgehalten, bevor man die… …   Lexikon der Economics

  • backtracking — v. go backwards; retrace one s footsteps or path …   English contemporary dictionary

  • backtracking — backˈtracking noun • • • Main Entry: ↑back …   Useful english dictionary

  • Backtracking-Verfahren —   [ bæktrækɪȖ , englisch »sich zurückziehen«], Versuch und Irrtum …   Universal-Lexikon

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.